# 题目描述
一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n-1 之内。在范围 0 ~ n-1 内的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
来源:LeetCode
# 思路
看到有序,就容易联想到二分法查找。
# 解法
/**
* @param {number[]} nums
* @return {number}
*/
const missingNumber = nums => {
let left = 0;
let right = nums.length - 1;
let middle = ~~((left + right) / 2);
while (left != middle) {
if (nums[middle] === middle) {
left = middle;
} else {
right = middle;
}
middle = ~~((left + right) / 2);
}
if (nums[right] === right) return right + 1;
if (nums[middle] === middle) return middle + 1;
return middle;
};